import random
class RandomQuickSort():
    def __init__(self):
        self.count = 0
    
    def partition(self,arr,low,high):
        i = low - 1
        pivotindex = random.randint(low, high)
        arr[pivotindex],arr[high] = arr[high],arr[pivotindex]
        for j in range(low,high):        
            if(arr[j]<=arr[high]):
                self.count+=1
                i = i+1
                arr[i],arr[j] = arr[j],arr[i]
        arr[i+1],arr[high] = arr[high],arr[i+1] 
        return (i+1) 
    def sort(self,arr,low,high):
        if low < high:
            pi = self.partition(arr, low, high)
            self.sort(arr, low, pi-1)
            self.sort(arr, pi+1, high)
    # 判断是否有序
    def isSorted(self,ls):
        for i in range(1,len(ls)):
            if ls[i]<ls[i-1]:
                return False
        return True